package swardToOffer.struct_1_arr;

/**
 * @Author ChanZany
 * @Date 2021/5/25 16:31
 * @Version 1.0
 * <p>
 * 面试题51：数组中的逆序对
 * 题目：在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组
 * 成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
 * 例子:
 * 输入: [7,5,6,4]
 * 输出: 5
 * 分析:[7,5],[7,6],[7,4],[5,4],[6,4]
 * 方法1:暴力破解O(N^2)
 * 方法2:归并排序O(NlogN)
 * 前面「分」的时候什么都不做，「合」的过程中计算「逆序对」的个数；
 *
 */
public class InversePairs {
    public int reversePairs1(int[] nums) {
        if (nums.length < 2) return 0;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int cur = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[i]) count++;
            }
        }
        return count;
    }

    int[] nums, tmp;

    public int reversePairs(int[] nums) {
        this.nums = nums;
        tmp = new int[nums.length];
        return mergeSort(0, nums.length - 1);
    }

    private int mergeSort(int l, int r) {
        // 终止条件
        if (l >= r) return 0;
        // 递归划分
        int m = (l + r) / 2;
        int res = mergeSort(l, m) + mergeSort(m + 1, r);
        // 合并阶段
        //1. 设置双指针 i:l->m , j:m+1->r 分别指向左 / 右子数组的首元素
        // 暂存数组 nums 闭区间 [i, r]内的元素至辅助数组 tmp ；
//        int i = l, j = m + 1;
//        for (int k = l; k <= r; k++)
//            tmp[k] = nums[k];
//        for (int k = l; k <= r; k++) {
//            //2.当 i = m + 1时：代表左子数组已合并完，因此添加右子数组当前元素 tmp[j]，并执行 j = j + 1；
//            if (i == m + 1)
//                nums[k] = tmp[j++];
//                //3.当 j = r + 1时：代表右子数组已合并完，因此添加左子数组当前元素 tmp[i] ，并执行 i = i + 1；
//                //4. 当tmp[i]≤tmp[j] 时：添加左子数组当前元素 tmp[i] ，并执行 i = i + 1
//            else if (j == r + 1 || tmp[i] <= tmp[j])
//                nums[k] = tmp[i++];
//                //5. 当tmp[i]>tmp[j] 时：添加右子数组当前元素 tmp[i] ，并执行 j = j + 1,此时构成m-i+1个逆序对,统计添加至res
//                // m-i+1的计算,如左子数组为[2,3,6] 右子树组为[0,1,4],此时i=0,j=0则可以生成的逆序对为[2,0][3,0][6,0],若此时i=1,则[3,0][6,0]
//            else {
//                nums[k] = tmp[j++];
//                res += m - i + 1; // 统计逆序对
//            }
//        }
        int i = l, j = m + 1, k = 0;
        while (i <= m && j <= r) {
            if  (nums[i] <= nums[j]) tmp[k++] =nums[i++];
            else {
                tmp[k++] =nums[j++];
                res += m-i+1;
            }
        }
        while (i <= m) tmp[k++] = nums[i++];
        while (j <= r) tmp[k++] = nums[j++];
        //将temp中的元素全部拷贝到原数组中
        k = 0;
        while (l <= r) nums[l++] = tmp[k++];
        return res;
    }


    public static void main(String[] args) {
        InversePairs Main = new InversePairs();
        System.out.println(Main.reversePairs(new int[]{7, 5, 6, 4}));
    }
}
